package dynamic;

/**
 * 题目：股票买卖的最大利润
 * 例如：
 *  [9,8,7,5,1,8] 这个股票在1位置买入，在8位置卖出是是最大利润7
 *  [9,8,7,6] 这个股票由于是一直在跌，所以没有利润
 * @Author Gavin
 * @date 2022.05.02 22:44
 */
public class solution_10 {
    /**
     * 第一种方式：暴力破解
     * 双层循环，处理数组中的任意数字组合
     *
     */
    //Time:O(n^2),Space:O(1)
    public int solution(int[] arr){
        if(arr.length<2)return 0;
        int max=0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                max=Math.max(max,arr[j]-arr[i]);
            }
        }
        return max;
    }
    /**
     * 第二种方式，动态规划
     */
    //Time:O(1),Space:O(1)
    public int solution_2(int[] arr){
        if(arr.length<2)return 0;
        int max=0,buyMin=arr[0];
        for (int i = 1; i < arr.length; i++) {
            if(arr[i]<buyMin)buyMin=arr[i];
            else{
                max=Math.max(max,arr[i]-buyMin);
            }
        }
        return max;
    }
}
